package com.lc.projects.structure.sort;

/***
 * 假设输入的线性表L的长度为n，L=L1,L2,..,Ln；线性表的元素属于有限偏序集S，|S|=k且k=O(n)，S={S1,S2,..Sk}；
 * 则计数排序可以描述如下： 1、扫描整个集合S，对每一个Si∈S，找到在线性表L中小于等于Si的元素的个数T(Si)；
 * 2、扫描整个线性表L，对L中的每一个元素Li，将Li放在输出线性表的第T(Li)个位置上，并将T(Li)减1。
 * 
 * 1 取出最大 最小值
 * 2 建立辅助数组，统计每个数字出现的次数
 * 3 辅助数组count[i] = count[i] + count[i - 1]; 累加
 * 4 遍历原数组，把原数组对应的值，放到目标数组对应的位置，辅助数组对应-1；
 * @author user
 *
 */
public class CountingSort {

	public static int[] sort(int[] nums) {
		int max = getMax(nums);
		int min = getMin(nums);

		int[] count = new int[max - min + 1];
		for (int i = 0; i < nums.length; i++) {
			count[nums[i] - min]++;
		}

		for (int i = 1; i < count.length; i++) {
			count[i] = count[i] + count[i - 1];
		}

		int[] result = new int[nums.length];
		for (int i = 0; i < result.length; i++) {
			result[count[nums[i] - min] - 1] = nums[i];
			count[nums[i] - min]--;
		}

		return result;
	}

	public static int getMax(int[] nums) {
		int max = nums[0];
		for (int i = 0; i < nums.length; i++) {
			if (nums[i] > max) {
				max = nums[i];
			}
		}
		return max;
	}

	public static int getMin(int[] nums) {
		int min = nums[0];
		for (int i = 0; i < nums.length; i++) {
			if (nums[i] < min) {
				min = nums[i];
			}
		}
		return min;
	}
}
